/**

This file is part of MaCI/GIMnet.

MaCI/GIMnet is free software: you can redistribute it and/or modify it 
under the terms of the GNU Lesser General Public License as published 
by the Free Software Foundation, either version 3 of the License, or 
(at your option) any later version.

MaCI/GIMnet is distributed in the hope that it will be useful, but WITHOUT 
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public 
License for more details.

You should have received a copy of the GNU Lesser General Public 
License along with GIMnet. (See COPYING.LESSER) If not, see 
<http://www.gnu.org/licenses/>.

**/
/**
 * \file
 * \brief Search structure for locating entries by string - implementation.
 * \author Antti Maula <antti.maula@tkk.fi>
 */
//*****************************************************************************
#include "strmap.h"
#include "owndebug.h"
#include <stdlib.h> // malloc
#include <string.h> // memset
#include <stdio.h>

// This module well tested, hence no asserts.
#define NDEBUG
#include <assert.h>

//*****************************************************************************
inline static TStrMapEntryBin *strMapFindBin(TStrMap *im, const char * const aKey);
static void strMapInitBinArray(TStrMap *im, const unsigned int aBinCount);
static void strMapBinInit(TStrMapEntryBin *imeb);
static int strMapBinAddEntry(TStrMapEntryBin *imeb, const char * const aKey, const void *aData);
static int strMapBinDeleteEntry(TStrMapEntryBin *imeb, const char * const aKey);
static TStrMapEntry *strMapBinFindEntry(TStrMapEntryBin *imeb, const char * const aKey);
inline static unsigned int strMapGetBinIndexByKey(TStrMap *im, const char * const aKey);
inline static TStrMapEntry *strMapEntryCreateAndInit(const char * const key,
                                                     const void *entry,
                                                     struct SStrMapEntry *prev,
                                                     struct SStrMapEntry *next);
inline static void strMapEntryDestroy(TStrMapEntry *ime);
//*****************************************************************************
//*****************************************************************************

TStrMap *strMapCreate()
{
  return (TStrMap *)malloc( sizeof(TStrMap) );
}
//*****************************************************************************

int strMapInit( TStrMap *im, 
               const unsigned int aHashBinCount)
{
  int result = -1;
  assert(im != NULL);
  
  ///// Init contents to zero.
  memset(im, 0x00, sizeof(TStrMap));

  ///// Init Map structures.
  strMapInitBinArray(im, aHashBinCount);

  // Done!
  result = 0;

  return result;
}
//*****************************************************************************

void strMapDeinit( TStrMap *im )
{
  int i;
  assert(im != NULL);
  
  for(i=0; i < im->hashBinCount; ++i) {
    // Take bin pointer
    TStrMapEntryBin *bin = &im->strMapEntryBins[i];

    // Take pointer to first element in bin.
    TStrMapEntry *e = bin->first;
    
    // Destroy elements in bin.
    while(e) {
      TStrMapEntry *del = e;
      e = e->next;
      strMapEntryDestroy(del);
    }
  }

  // Destroy bin array.
  free(im->strMapEntryBins);
  im->strMapEntryBins = NULL;
}
//*****************************************************************************

void strMapDestroy( TStrMap *im )
{
  assert(im != NULL);
  free(im);
}
//*****************************************************************************

void strMapClear(TStrMap *im)
{
  int i;
  for(i=0; i < im->hashBinCount; ++i) {
    TStrMapEntryBin *bin = &im->strMapEntryBins[i];
    TStrMapEntry *e = bin->first;
    
    // Clear bin. (first entry pointer is stored before above)
    bin->first = NULL;
    bin->entryCount = 0;

    // Destroy elements.
    while(e) {
      TStrMapEntry *del = e;
      strMapEntryDestroy(del);
      e = e->next;
    }
  }
}
//*****************************************************************************

int strMapAddEntry(TStrMap *im, const char * const aNodeSTR, const void *aEntry)
{
  int result = -1;
  assert(im != NULL);

  // Get correct Bin.
  TStrMapEntryBin *b = strMapFindBin(im, aNodeSTR);
  assert(b != NULL);

  // Add to bin.
  result = strMapBinAddEntry(b, aNodeSTR, aEntry);

  return result;
}
//*****************************************************************************

int strMapDeleteEntry(TStrMap *im, const char * const aNodeSTR)
{ 
  int result = -1;
  assert(im != NULL);

  // Get correct Bin.
  TStrMapEntryBin *b = strMapFindBin(im, aNodeSTR);
  assert(b != NULL);
  
  // Add to bin.
  result = strMapBinDeleteEntry(b, aNodeSTR);

  return result;
}
//*****************************************************************************

const TStrMapEntry *strMapGetEntry(TStrMap *im, const char * const aNodeSTR)
{ 
  assert(im != NULL);

  // Get correct Bin.
  TStrMapEntryBin *b = strMapFindBin(im, aNodeSTR);
  assert(b != NULL);
  
  // Add to bin.
  return strMapBinFindEntry(b, aNodeSTR);
}
//*****************************************************************************

void strMapGetNextEntryIterator(TStrMap *im, TStrMapEntryIterator *aIter)
{
  assert(im != NULL);
  assert(aIter != NULL);
  
  aIter->bin = 0;
  const TStrMapEntryBin *b = &im->strMapEntryBins[0];
  aIter->entry = b->first;
}
//*****************************************************************************

const TStrMapEntry *strMapGetNextEntry(TStrMap *im, TStrMapEntryIterator *aIter)
{
  const TStrMapEntry *e = NULL;
  assert(im != NULL);
  assert(aIter != NULL);

  if (aIter->entry) {
    e = aIter->entry;
    aIter->entry = e->next;

  } else {
    aIter->bin++;
    if (aIter->bin < im->hashBinCount) {
      const TStrMapEntryBin *b = &im->strMapEntryBins[aIter->bin];
      if (b->first != NULL) {
        e = b->first;
        aIter->entry = b->first->next;

      } else {
        e = strMapGetNextEntry(im, aIter);

      }
    } 
  }

  return e;
}
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************

inline static TStrMapEntryBin *strMapFindBin(TStrMap *im, const char * const aKey)
{
  return &im->strMapEntryBins[strMapGetBinIndexByKey(im, aKey)];
}
//*****************************************************************************

inline static void strMapEntryDestroy(TStrMapEntry *ime)
{
  if (ime->key) free(ime->key);
  free(ime);
}
//*****************************************************************************

inline static unsigned int strMapGetBinIndexByKey(TStrMap *im, const char * const aKey)
{
  unsigned int i, final;
  unsigned int h = 0, ho;
  const int len = strlen(aKey);
  
  // Calculate hash to FIRST '.' found. (Should eliminate the extension from the name)
  for(i=0; i < len; ++i) {
    ho = h & 0xf8000000;
    h = h << 5;
    h ^= (ho >> 27);
    h ^= (unsigned char)aKey[i];
  }
  final = h % im->hashBinCount;
  return final;
}
//*****************************************************************************

static void strMapInitBinArray(TStrMap *im, 
                              const unsigned int aBinCount)
{
  int i;
  assert(im->strMapEntryBins == NULL);
  
  // Allocate bins.
  im->hashBinCount = aBinCount;
  im->strMapEntryBins = (TStrMapEntryBin *)malloc( sizeof(TStrMapEntryBin) * im->hashBinCount );
  assert(im->strMapEntryBins != NULL);

  dPrint(ODDEBUG(0),"strMap %p: Reserved %lu bytes for the Hash table", 
         im, (long unsigned)(sizeof(TStrMapEntryBin) * im->hashBinCount));

  // Initialize bins.
  for(i=0; i < aBinCount; ++i) {
    strMapBinInit(&im->strMapEntryBins[i]);
  }
}
//*****************************************************************************

inline static TStrMapEntry *strMapEntryCreateAndInit(const char * const key,
                                                   const void *entry,
                                                   struct SStrMapEntry *prev,
                                                   struct SStrMapEntry *next)
{
  TStrMapEntry *ime = (TStrMapEntry *)malloc(sizeof(TStrMapEntry));
  assert(ime != NULL);

  // ALLOCATE
  const int keylen = strlen(key)+1;
  ime->key = (char*)malloc(keylen);
  assert(ime->key != NULL);
  memcpy(ime->key, key, keylen);

  ime->entry = entry;
  ime->prev = prev;
  ime->next = next;
  return ime;
}
//*****************************************************************************

static void strMapBinInit(TStrMapEntryBin *imeb)
{
  // Zero entries, 1 reserved (initial, allows realloc by
  // strMapResizeBin())
  imeb->entryCount = 0;

  // Mark empty.
  imeb->first = NULL;
}
//*****************************************************************************

static int strMapBinAddEntry(TStrMapEntryBin *imeb, const char * const aKey, const void *aData)
{
  int result = -1;

  // Create new entry.
  TStrMapEntry *newentry = strMapEntryCreateAndInit(aKey, aData, NULL, NULL);

  assert(imeb != NULL);

  // Take first entry.
  TStrMapEntry *e = imeb->first;
  
  if (!e) {
    imeb->first = newentry;
    result = 0;

  } else {

    while(e) {
      const int compare = strcmp(e->key, aKey);
      if (compare == 0) {
        // Exact match found. Failure.
        strMapEntryDestroy(newentry);
        break;
        
      } else if (compare > 0) {
        // We passed the point where the key can exist, so insert before this.
        newentry->next = e;
        newentry->prev = e->prev;
        if (e->prev) {
          e->prev->next = newentry;
        } else {
          imeb->first = newentry; 
        }
        e->prev = newentry;
    
        result = 0;
        break;

      } else if (e->next == NULL) {
        // This was the last entry.
        e->next = newentry;
        newentry->prev = e;
        result = 0;
        break;
        
      }
      e = e->next;
    }
  }

  ++imeb->entryCount;

  return result;
}
//*****************************************************************************

static int strMapBinDeleteEntry(TStrMapEntryBin *imeb, const char * const aKey)
{
  int result = -1;

  TStrMapEntry *e = strMapBinFindEntry(imeb, aKey);
  if (e) {

    // Remove entry from chain.
    if (e->prev) {
      // Previous exists, so marks its next as deleted items next.
      e->prev->next = e->next;
      if (e->next) e->next->prev = e->prev;

    } else {
      // Previous doesn't exist, so mark first element as deleted
      // items next.
      imeb->first = e->next;
      if (e->next) e->next->prev = NULL;
    }

    // Delete allocated entry
    strMapEntryDestroy(e);

    // Update stats.
    imeb->entryCount --;

    // update result
    result = 0;
  }

  return result;
}
//*****************************************************************************

static TStrMapEntry *strMapBinFindEntry(TStrMapEntryBin *imeb, 
                                      const char * const aKey)
{
  TStrMapEntry *f = imeb->first;
  while(f) {
    const int compare = strcmp(f->key, aKey);
    if (compare == 0) {
      // Node was found.
      return f;
      
    } else if (compare > 0) {
      // We passed the ordered place of entry.
      return NULL; 
      
    } else {
      f = f->next;
      
    }
  }
  return NULL;
}
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
//*****************************************************************************
/* 
   gcc -g3 -lpthread -lrt -Wall -DLINUX_OS -DSTRMAP_UNIT_TEST -pg -I ../utils ../utils/ownutils.c ../utils/owndebug.c strmap.c
   ./a.out
   valgrind -v ./a.out
*/
//*****************************************************************************

#ifdef STRMAP_UNIT_TEST
#include "ownutils.h"
#include <stdio.h>
int main(int argc, char *argv[])
{
  int i;
  TStrMap strm;
  unsigned int bins = 3;
  unsigned int dataelements = 10;
  ownTime_ms_t btime;
  ownTime_ms_delta_t since;
  float tperentry;
  char str[100];

  if (argc > 1) {
    dataelements = atoi(argv[1]);
  }
  if (argc > 2) {
    bins = atoi(argv[2]);
  }


  btime = ownTime_get_ms();
  printf("Init TStrMap with %u bins\n", bins);
  strMapInit(&strm, bins);
  printf("... Completed, in %ld milliseconds\n", ownTime_get_ms_since(btime));



  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    strMapAddEntry(&strm, str, (const void*)&i);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Query %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    const TStrMapEntry *e = strMapGetEntry(&strm, str);
    assert(e != NULL);
    assert(e->entry == (void*)&i);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);

  

  btime = ownTime_get_ms();
  printf("Delete %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) { 
    sprintf(str,"paskaaa-saatana-%d", i);
    assert( strMapDeleteEntry(&strm, str) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);



  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    assert( strMapAddEntry(&strm, str, (void*)&i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);



  btime = ownTime_get_ms();
  printf("Query %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    const TStrMapEntry *e = strMapGetEntry(&strm, str);
    assert(e != NULL);
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Delete %u entries in reverse order\n", dataelements);
  for(i=dataelements-1; i >= 0; --i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    assert( strMapDeleteEntry(&strm, str) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);


  btime = ownTime_get_ms();
  printf("Adding %u entries...\n", dataelements);
  for(i=0; i < dataelements; ++i) {
    sprintf(str,"paskaaa-saatana-%d", i);
    assert( strMapAddEntry(&strm, str, (void*)&i) == 0 );
  }
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);

  btime = ownTime_get_ms();
  printf("Iterating %u entries...\n", dataelements);
  int n = 0;
  TStrMapEntryIterator ei;
  strMapGetNextEntryIterator(&strm, &ei);
  const TStrMapEntry *e;

  do {
    e = strMapGetNextEntry(&strm, &ei);
    if (e) {
      n++;
      if (argc == 4) printf("'%s', ", e->key);
    }
  } while (e);
  if (argc == 4) printf("\n");
  assert( n == dataelements );
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);




  btime = ownTime_get_ms();
  printf("calling strMapDeinit, with %u entries still in table...\n", dataelements);
  strMapDeinit(&strm);
  since = ownTime_get_ms_since(btime);
  tperentry = 1000.0 * (float)since / (float)dataelements;
  printf("... Completed, in %ld milliseconds. (%.2fus / entry)\n", since, tperentry);

  return 0;
}
#endif
//*****************************************************************************

